package acwing_02;


import java.util.Scanner;

public class _831_KMP字符串 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		String P = scan.next();
		int m = scan.nextInt();
		String S = scan.next();
		int next[] = new int[n+1];
		char[] p = new char[n+1];
		char[] s = new char[m+1];
		
		StringBuilder str = new StringBuilder();
		
		// 从下标1开始存模板串P的值
		for(int i = 1; i <= n; i++) {
			p[i] = P.charAt(i - 1);
		}
		// 从下标1开始存长串S的值
		for(int i = 1; i <= m; i++) {
			s[i] = S.charAt(i - 1);
		}

		// 对模式串p构造next数组
		// 从下标1开始存储
		// 第1个元素永远是0，所以从第2个元素开始
		for(int i = 2,j = 0;i <= n; i++) {
			// 如果j==0说明完全没匹配的前缀，不需要进入循环
			// 如果j!=0说明有匹配的前缀，而此时如果i和前缀后1位元素的值不匹配，则说明前缀不匹配，需要往前移动前缀
			while(j != 0 && p[i] != p[j + 1]) {
				/* 
				 * 如果j = 2说明以及匹配了模板字符串P的前2个字符，
				 * 如果进入这里说明下一个字符不相匹配，则需要访问next[2]的元素，
				 * next数组内元素的值存的是该位置元素匹配的前缀 
				 * 如果next[2]的值是1，说明第2个元素匹配了模板字符串P的前1个字符
				 * 于是拿这个前缀的下一个字符(就是p[j+1])，跟p[i]进行匹配，如果匹配则可以从这个位置的前缀+1，如果不匹配则继续进入next[j]，直到0
				 * 如果next[2]的值是0，说明没有匹配的前缀，就不会进入这里的while
				 * */
				j = next[j];
			}
			// 如果当前值与前缀后一个值相同，说明前j+1个前缀是相同的，则j++说明多了一个匹配的前缀
			if(p[i] == p[j + 1]) {
				j++;
			}
			// 存储第i个元素匹配的前缀j的值
			// 表示到当前位置，对于模板串P，有j个前缀是相同的
			next[i] = j;
		}
		
		// 对长串S进行匹配模板串P
		// 原理与上面构造next数组相似
		for(int i = 1,j = 0; i <= m;i++) {
			// 当长串值与模板前缀下一个值不同，则前缀往前跳
			while(j != 0 && s[i] != p[j+1]) {
				j = next[j];
			}
			// 长串值与前缀后一个值相同，则前缀+1
			if(s[i] == p[j+1]) {
				j++;
			}
			// 当前缀值的长度跟模板串的长度相同，说明匹配到与模板相同的串
			// 当前长度-模板串长度 就是S中相同串的起点下标
			// 匹配到后需要把j往上一个最匹配的前缀跳，才能继续匹配，否则j再加下去会超过模板串的大小
			if(j == n) {
				str.append(i - n + " ");
				j = next[j];
			}
		}

		System.out.print(str.toString());
		scan.close();
		
	}
}
